package l.l.w.leetcode.MergeKSortedLists;


/**
 * Created by llw on 2017/10/29.
 */
public class MergeKSortedLists {
    /**
     * 这种方法会超时。
     * @param lists
     * @return
     */
    /*
    public ListNode mergeKLists(ListNode[] lists) {

        ListNode head= null;
        ListNode cur = null;
        int nums = lists.length;
        int index = 0;
        boolean flag = true;
        ListNode min_store = new ListNode(Integer.MAX_VALUE);
        ListNode min = min_store;
        for(int i = 0; i < nums; ++i){
            if(lists[i] != null ){
                flag = false;
                if(lists[i].val < min.val){
                    min = lists[i];
                    index = i;
                }
            }
        }
        if(flag) return null;
        head = lists[index];
        cur = head;
        lists[index] = lists[index].next;
        while(true){
            flag = true;
            min = min_store;
            for(int i = 0; i < nums; ++i){
                if(lists[i] != null){
                    flag = false;
                    if(lists[i].val < min.val){
                        min = lists[i];
                        index = i;
                    }
                }
            }
            if(flag) break;
            cur.next = min;
            cur = cur.next;
            lists[index] = lists[index].next;

        }
        return head;
    }*/
    public ListNode mergeKLists_new(ListNode[] lists) {
        int heapSize = partition(lists);
        if(heapSize == 0) return null;
        if(heapSize ==1) return lists[0];
        for(int i = heapSize/2; i >=0 ;--i){
            down(lists,i,heapSize);
        }
        ListNode head = lists[0];
        if(head == null){
            return head;
        }
        ListNode cur = head;
        lists[0] = lists[0].next;
        if(lists[0]!= null && lists[0].val <= lists[heapSize-1].val){
            down(lists,0,heapSize);
        }else{
            exchange(lists,0,heapSize-1);
            if(lists[heapSize-1] == null)heapSize--;
            down(lists,0,heapSize);
        }
        while(heapSize !=0){
            if(lists[0]!= null){
                cur.next = lists[0];
                cur = cur.next;
                lists[0] = lists[0].next;
                if(lists[0]!= null && lists[0].val <= lists[heapSize-1].val){
                    down(lists,0,heapSize);
                }else{
                    exchange(lists,0,heapSize-1);
                    if(lists[heapSize-1] == null)heapSize--;
                    down(lists,0,heapSize);
                }

            }else{
                break;
            }
        }
        return head;
    }

    private void down(ListNode[] lists,int i,int heapSize) {
//        int i =0;
        int left,right,min = i;
        while(i < heapSize){
            left = 2*i+1;
            right = 2*i+2;
            if(left < heapSize && lists[left] != null && lists[left].val < lists[min].val){
                min = left;
            }
            if(right < heapSize && lists[right] != null && lists[right].val < lists[min].val){
                min = right;
            }
            if(min ==i) break;
            else{
                exchange(lists,i,min);
                i = min;
            }
        }
    }

    private int partition(ListNode[] lists) {
        int j = 0;
        for(int i = 0; i < lists.length ;++i){
            if(lists[i] != null){
                j++;
                exchange(lists,i,j-1);
            }
        }
        return j;
    }

    private void min_up(ListNode[] lists, int i, int heapSize) {
        int left,right,min = i;
        left = 2*i+1;
        right = 2*i+2;
        if(left < heapSize && lists[left] != null && lists[left].val < lists[min].val){
            min = left;
        }
        if(right < heapSize &&lists[right] != null && lists[right].val < lists[min].val){
            min = right;
        }
        if(min ==i) ;
        else{
            exchange(lists,i,min);
        }
    }

    private void exchange(ListNode[] lists, int i, int j) {
        ListNode temp = lists[i];
        lists[i] = lists[j];
        lists[j] = temp;
    }

    public static void main(String[] args) {
//        [[-6,-3,-1,1,2,2,2],[-10,-8,-6,-2,4],[-2],[-8,-4,-3,-3,-2,-1,1,2,3],[-8,-6,-5,-4,-2,-2,2,4]]
        ListNode l0 = null;

        ListNode l1 = new ListNode(-6);
        ListNode l12 = new ListNode(-3);
        ListNode l13 = new ListNode(-1);
        ListNode l14 = new ListNode(1);
        ListNode l15 = new ListNode(2);
        ListNode l16 = new ListNode(2);
        ListNode l17 = new ListNode(2);
        l16.next = l17;
        l15.next = l16;
        l14.next = l15;
        l13.next = l14;
        l12.next = l13;
        l1.next = l12;
        ListNode l2 = new ListNode(-10);
        ListNode l22 = new ListNode(-8);
        ListNode l23 = new ListNode(-6);
        ListNode l24 = new ListNode(-2);
        ListNode l25 = new ListNode(4);
        l24.next = l25;
        l23.next = l24;
        l22.next = l23;
        l2.next = l22;

        ListNode l3 = new ListNode(-8);
        ListNode l32 = new ListNode(-4);
        ListNode l33 = new ListNode(-3);
        ListNode l34 = new ListNode(-3);
        ListNode l35 = new ListNode(-2);
        ListNode l36 = new ListNode(-1);
        ListNode l37 = new ListNode(1);
        ListNode l38 = new ListNode(2);
        ListNode l39 = new ListNode(3);
        l38.next = l39;
        l37.next = l38;
        l36.next = l37;
        l35.next = l36;
        l34.next = l35;
        l33.next = l34;
        l32.next = l33;
        l3.next = l32;
//        [-8,-6,-5,-4,-2,-2,2,4]
        ListNode l4 = new ListNode(-8);
        ListNode l42 = new ListNode(-6);
        ListNode l43 = new ListNode(-5);
        ListNode l44 = new ListNode(-4);
        ListNode l45 = new ListNode(-2);
        ListNode l46 = new ListNode(-2);
        ListNode l47 = new ListNode(2);
        ListNode l48 = new ListNode(4);
        l47.next = l48;
        l46.next = l47;
        l45.next = l46;
        l44.next = l45;
        l43.next = l44;
        l42.next = l43;
        l4.next = l42;

        ListNode l5 = new ListNode(-2);
//        l2.next = new ListNode(5);
//        l1.next = l2;
        ListNode[] nodes = new ListNode[6];
        nodes[0] = l0;
        nodes[1] = l1;
        nodes[2]=l2;
        nodes[3] = l3;
        nodes[4] = l4;
        nodes[5] = l5;
        ListNode result = new MergeKSortedLists().mergeKLists_new(nodes);
        System.out.println(result);
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
